#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int findKthLargest(int* nums, int numsSize, int k);

void sift_down(int* heap, int size);

int main()
{
	return 0;
}

int findKthLargest(int* nums, int numsSize, int k)
{
	int* heap = malloc(k * sizeof(int));
	memset(heap, -10001, k);

	for (int idx = 0; idx < numsSize; idx++) {
		int num = nums[idx];
		if (num > heap[0]) {
			heap[0] = num;
			sift_down(heap, k);
		}
	}

	/* for (int i = 0; i < k; i++) */
	/* printf("i:%d\t", heap[i]); */
	return heap[0];
}

void sift_down(int* heap, int size)
{
	int idx = 0,
		leftIdx = (idx << 1) + 1;

	while (leftIdx < size) {
		int left = leftIdx;
		if (left + 1 < size && heap[left + 1] < heap[left])
			left++;

		if (heap[idx] > heap[left]) {
			int temp = heap[idx];
			heap[idx] = heap[left];
			heap[left] = temp;

			idx = left;
			leftIdx = (idx << 1) + 1;
		} else break;
	}
}
